#pragma once
#include <iostream>
#include <utility>
#include <cassert>
#include <ctime>
#define M 3
//B树的节点
template<class K, class V, size_t MM = M>
struct bTreeNode
{
	size_t _n = 0;                                   //关键字个数
	std::pair<K, V> _val[M];                         //关键字数组      
	bTreeNode<K, V>* _child[M + 1];                  //孩子个数
	bTreeNode<K, V>* _parent = nullptr;              //父节点
	bTreeNode()
	{
		size_t i = 0;
		for (; i < M; i++)
		{
			_val[i] = std::pair<K, V>();
			_child[i] = nullptr;
		}
		_child[i] = nullptr;
	}
};

//B树的实现
template<class K, class V, size_t MM = M>
class bTree
{
	typedef bTreeNode<K, V> node;
public:
	bTree() = default;
	// 查找函数
	std::pair<node*, int> Find(K key)
	{
		assert(_root != nullptr);
		node* cur = _root;
		node* parent = nullptr;
		size_t i = 0;
		bool button = false;
		while (cur)
		{
			i = 0;
			for (; i < cur->_n; i++)
			{
				if (key > cur->_val[i].first)
					continue;
				if (key < cur->_val[i].first)
				{
					button = true;
					parent = cur;
					cur = cur->_child[i];
					break;
				}
				if (key == cur->_val[i].first)
					return std::make_pair(nullptr, -1);
			}
			if (!button)
			{
				parent = cur;
				cur = cur->_child[i];
			}
			button = false;
		}
		return std::make_pair(parent, i);
	}
	// 插入函数
	bool insert(const std::pair<K, V>& val)
	{
		//如果为空节点的情况下
		if (_root == nullptr)
		{
			node* newnode = new node;
			newnode->_val[0] = val;
			_root = newnode;
			_root->_parent = nullptr;
			(_root->_n)++;
			return true;
		}
		//先查找
		std::pair<node*, int> ret = Find(val.first);
		//判断是否存在，不存在就插入
		if (ret.first != nullptr)
		{
			// 挪动数据并且插入值
			for (int i = ret.first->_n; i > ret.second; i--)
				ret.first->_val[i] = ret.first->_val[i - 1];
			ret.first->_val[ret.second] = val;
			(ret.first->_n)++;
			//判断是否需要分裂
			while (1)
			{
				//判断是否需要分裂
				bool isSplit = check(ret.first);
				//叶子结点为空
				if (isSplit)
				{
					if (ret.first->_parent == nullptr)
					{
						node* brother = new node;
						node* newroot = new node;
						int j = 0;
						//保留拷贝节点的数量
						int change = ret.first->_n / 2;
						//拷贝节点和孩子指针
						for (int i = ret.first->_n / 2; i > 0; i--)
						{
							brother->_val[j] = ret.first->_val[ret.first->_n - 1];
							brother->_child[j] = ret.first->_child[ret.first->_n - 1];
							ret.first->_val[ret.first->_n - 1] = std::pair<K, V>();
							ret.first->_child[ret.first->_n - 1] = nullptr;
							(brother->_n)++;
							j++;
						}
						brother->_child[j] = ret.first->_child[ret.first->_n];
						ret.first->_child[ret.first->_n] = nullptr;
						ret.first->_n = ret.first->_n - ret.first->_n / 2;
						
						
						//改变孩子节点的父亲节点
						int k = 0;
						for (; k < change; k++)
						{
							if (brother->_child[k])
								brother->_child[k]->_parent = brother;
						}
						if (brother->_child[k])
							brother->_child[k]->_parent = brother;
						
						//孩子指针拷贝完成
						newroot->_val[0] = ret.first->_val[ret.first->_n - 1];
						(newroot->_n)++;
						ret.first->_val[ret.first->_n - 1] = std::pair<K, V>();
						(ret.first->_n)--;
						newroot->_child[0] = ret.first;
						newroot->_child[1] = brother;
						brother->_parent = newroot;
						ret.first->_parent = newroot;
						_root = newroot;
						break;
					}
					//叶子节点不为空
					else
					{
						node* brother = new node;
						int j = 0;
						int change = ret.first->_n / 2;
						for (int i = ret.first->_n / 2; i > 0; i--)
						{
							brother->_val[j] = ret.first->_val[ret.first->_n - 1];
							brother->_child[j] = ret.first->_child[ret.first->_n - 1];
							ret.first->_val[ret.first->_n - 1] = std::pair<K, V>();
							ret.first->_child[ret.first->_n - 1] = nullptr;
							(brother->_n)++;
							j++;
						}
						brother->_child[j] = ret.first->_child[ret.first->_n];
						ret.first->_child[ret.first->_n] = nullptr;
						ret.first->_n = ret.first->_n - ret.first->_n / 2;

						//改变孩子节点的父亲节点
						int k = 0;
						for (; k < change; k++)
						{
							if (brother->_child[k])
								brother->_child[k]->_parent = brother;
						}
						if (brother->_child[k])
							brother->_child[k]->_parent = brother;

						//走到这里一定是拷贝完成，但是还没有往父亲节点提取中位数
						std::pair<K, V> inserti = ret.first->_val[ret.first->_n - 1];
						ret.first->_parent->_val[ret.first->_parent->_n] = ret.first->_val[ret.first->_n - 1];
						ret.first->_val[ret.first->_n - 1] = std::pair<K, V>();
						(ret.first->_parent->_n)++;
						(ret.first->_n)--;
						//提取中位数完毕，开始排父节点的顺序
						int pos = insertSort(ret.first->_parent->_val, ret.first->_parent->_n, inserti);
						if (pos + 1!= ret.first->_parent->_n)
						{
							//挪动孩子指针
							for (int i = ret.first->_parent->_n + 1; i > pos; i--)
								ret.first->_parent->_child[i] = ret.first->_parent->_child[i - 1];
						}
						ret.first->_parent->_child[pos] = ret.first;
						ret.first->_parent->_child[pos + 1] = brother;
						brother->_parent = ret.first->_parent;
						ret.first = ret.first->_parent;
					}
				}
				else
					break;
			}
			return true;
		}
		else
			return false;
	}
	void Print()
	{
		print(_root);
	}
private:
	node* _root = nullptr;
	bool check(node* cur)
	{
		assert(cur != nullptr);
		if (cur->_n > M - 1 /*|| cur->_n == M / 2*/)
			return true;
		else
			return false;
	}
	int insertSort(std::pair<K, V>* arr, int num,const std::pair<K, V>& val)
	{
		int end = num - 2;
		while (end >= 0)
		{
			if (arr[end].first > val.first)
				end--;
			else if (arr[end].first < val.first)
			{
				for (int i = num - 1; i > end; i--)
					arr[i] = arr[i - 1];
				arr[end + 1] = val;
				return end + 1;
			}
		}
		if (num == 2)
		{
			end = 0;
			if (arr[end].first > val.first)
			{
				arr[end + 1] = arr[end];
				arr[end] = val;
				return end;
			}
			else
				return end + 1;
		}
		if (end < 0)
		{
			for (int i = num - 1; i > 0; i--)
				arr[i] = arr[i - 1];
			arr[0] = val;
			return 0;
		}
		return -1;
	}
	void print(node* cur)
	{
		if (cur == nullptr)
			return;
		size_t i = 0;
		for (; i < cur->_n; i++)
		{
			print(cur->_child[i]);
			std::cout << cur->_val[i].first << std::endl;
		}
		print(cur->_child[i]);
	}
};

